import java.util.ArrayList;
import java.util.List;

/**
 * 994. Rotting Oranges 腐烂的橘子
 * https://leetcode.com/problems/rotting-oranges/description/
 */
class RoatingOranges {
    private static final int[][] DIRECTIONS = {{-1, 0}, {1, 0}, {0, -1}, {0, 1}}; // 四方向
    /**
     * 方法：使用广度优先搜索（BFS）模拟橘子腐烂过程，统计所有橘子腐烂所需时间
     * 
     * Args:
     *   grid: int[][] - 表示橘子状态的二维数组，0表示空单元格，1表示新鲜橘子，2表示腐烂橘子
     * 
     * Returns:
     *   int - 所有橘子腐烂所需的最少分钟数，如果无法使所有橘子腐烂则返回-1
     * 
     * Time: O(M*N) - 需要遍历整个网格，M和N分别是网格的行数和列数
     * Space: O(M*N) - 最坏情况下队列可能存储所有腐烂的橘子
     */
    public int orangesRotting(int[][] grid) {
        int m = grid.length, n = grid[0].length;
        int fresh = 0;
        List<int[]> queue = new ArrayList<>();
        for(int i = 0; i < m; i++){
            for(int j = 0; j < n; j++){
                if(grid[i][j] == 1){
                    fresh++;// 统计新鲜橘子个数
                } else if (grid[i][j] == 2){
                    queue.add(new int[]{i, j});
                }
            }
        }
        int minute = 0;
        while (fresh > 0 && !queue.isEmpty()){
            minute++;
            List<int[]> tmp = queue;
            queue = new ArrayList<>();
            for(int[] pos : tmp){
                for(int[] d : DIRECTIONS){
                    int i = pos[0] + d[0];
                    int j = pos[1] + d[1];
                    if (0 <= i && i < m && 0 <= j && j < n && grid[i][j] == 1){
                        fresh--;
                        grid[i][j] = 2;
                        queue.add(new int[]{i, j});
                    }
                }
            }
        }
        return fresh > 0 ? -1: minute;
    }
}